<?php
/*
 * 规定1是丑数，其他的数如果只含有2或3或5的因子，那么这个数也是丑数。
 * 比如依次的丑数为：1,2,3,4,5,6,8,9,10,12,15...
 * 求第n个丑数
 */

$n = 30;
$obj      = new Code_01_UglyNumber();
var_dump($obj->do1($n));
var_dump($obj->do2($n));

class Code_01_UglyNumber
{
    // 强行计算每个数是否丑数
    public function do1($n)
    {
        $number = 0;
        $count = 0;
        while ($count < $n) {
            ++$number;
            if ($this->isUgly($number)) {
                $count++;
            }
        }
        return $number;
    }

    // 第i个丑数，可以由之前某个丑数 或乘2 或乘3 或乘5 得到
    public function do2($n)
    {
        $help = array_fill(0, $n, null);
        $help[0] = 1;
        $i2 = $i3 = $i5 = 0;
        $index = 1;
        while ($index < $n) {
            $help[$index] = min(2 * $help[$i2], 3 * $help[$i3], 5 * $help[$i5]);
            if ($help[$index] == 2 * $help[$i2]) {
                $i2++;
            }
            if ($help[$index] == 3 * $help[$i3]) {
                $i3++;
            }
            if ($help[$index] == 5 * $help[$i5]) {
                $i5++;
            }
            $index++;
        }
        return $help[$index - 1];
    }


    protected function isUgly($num)
    {
        while ($num % 2 == 0) {
            $num = $num / 2;
        }
        while ($num % 3 == 0) {
            $num = $num / 3;
        }
        while ($num % 5 == 0) {
            $num = $num / 5;
        }
        return $num == 1;
    }

}